'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-23 14:40:06
'''
'''
如果已知一个带环链表，如何判断环的入口

tips:用快慢指针判断是否带环。依据是快指针与慢指针会在环内相遇。设环外部分为L,环大小为N，相遇时慢指针再环内
走了a。这样的话有
2*(L+a) - (L+a) = kN
如此有 L  = (k-1)*N + (N-a) #(N-a)不正是这个时候慢指针到下次入口时候的距离嘛？
这个方程式意味着慢指针再走L肯定能到出口了。 这个时候再在开始设置一个慢指针，让它与满指针再一起走，他们
定会再入口处相遇。
这个方法用了三个指针，很有意思。
'''

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution:
    def FindEnterLoop(self, head):
        fast = head
        slow = head
        find = head
        count = 0
        while fast and slow:
            fast = fast.next
            slow = slow.next
            # find指针的移动只能放这，必须同步移动，不然错过去就进入死循环了
            if count:
                find = find.next
            # print(slow.val)
            if fast:
                fast = fast.next
            if fast == slow:
                count += 1
            
            if find == slow:
                return find

if __name__ == "__main__":
    head = ListNode(3)
    tmp = ListNode(2)
    head.next = tmp
    tmp2 = ListNode(0)
    tmp.next = tmp2
    tmp2 = ListNode(4)
    tmp.next.next = tmp2
    tmp2.next = tmp

    solution = Solution()
    haha = solution.FindEnterLoop(head)
    print(haha.val)